This invention relates to a method of and apparatus for digital data storage.
The growing importance of digital media places increasingly severe demands on the resources within a distributed system, particularly as regards network bandwidth and data storage. Faster client and server systems and increasingly large and sophisticated media files lead to increased expectations by users of being able to access and manipulate these files easily. Whilst bandwidth issues receive much attention from the designers of the systems that handle digital media, the high cost of storing digital media is becoming significant, despite the falling costs of many kinds of storage.
The traditional approach to reducing digital media storage costs is to migrate little used material from on-line delivery platforms, such as the hard drives of PCs and servers, onto lower cost archival storage, such as tape. The cost and delay in retrieving such archived media and delivering it on-line can be quite considerable, however. This cost is becoming increasingly apparent to system designers.
Another approach to reducing data storage costs is to retain digital data within the on-line delivery system, but to compress it. Compression technology can significantly increase the amount of material available on-line, but may degrade the material and thus imposes a uniform level of quality. This may be below the minimum quality threshold for some users. It is not always possible to know a priori the requirements of all the users for the media and conventionally there is no mechanism for recovering quality once it has been lost. Hence, traditional compression approaches are inherently limited.
One of the problems of compression schemes is that they take no account of the varied and possibly conflicting requirements made upon the media by the shared access of multiple clients. Most compression schemes utilise an xe2x80x9call-or-nothingxe2x80x9d principle: until the media is completely delivered and fully decoded, the user cannot browse or examine it in order to decide whether it is what they wanted. If not, then there is no option but to discard it completely. This is obviously an inefficient use of resources.
Recent work has concentrated on improving the usability of media over networks, and reduce inefficient use of network resources, by introducing xe2x80x9cprogressivexe2x80x9d compression schemes
One such xe2x80x98progressivexe2x80x99 scheme is disclosed in U.S. Pat. No. 5,880,856 to Microsoft Corporation, which teaches a particular approach to the use of wavelet transforms. In the U.S. Pat. No. 5,880,856 patent, an image is transformed using the wavelet transformation to yield 4 or 5 decomposition levels, with a base decomposition level giving a low resolution image, and increasingly higher decomposition levels giving higher resolution images. The client receives initially only the base decomposition level data, but the low resolution image resulting from the base decomposition level data gradually sharpens up as higher decomposition levels are received and decoded. Sharpening up of the image occurs as a result of 2 factors: first, as all of the 4 sub-bands which form each decomposition level are received and decoded, the image quality level increases slightly. As successive decomposition levels are received and decoded, the image quality increases more significantly. One characteristic of the system taught in the U.S. Pat. No. 5,880,856 patent is that the sub-bands and decomposition levels are all transmitted to clients in the same, fixed order, which is relatively inflexible. Whilst this scheme allows the client control over quality, it provides no other parameters that can be controlled.
Further reference may be made to the paper by Beong-Jo Kim, Zixiang Xiong and William Pearlman, xe2x80x9cVery Low Bit-Rate Embedded Coding with 3D Set Partitioning in Hierarchical Treesxe2x80x9d, submitted to IEEE Trans. Circuits and Systems for Video Technology, Special Issue on Image and Video Processing for Emerging Interactive Multimedia Services, September 1998. This paper discloses applying a SPIHT compression scheme to a wavelet-based transform, which yields a bitstream encoding multiple spatial resolutions, with progressive quality ordering within a given spatial resolution, as in the U.S. Pat. No. 5,880,856 patent.
Another system for scalable video transmission is disclosed in U.S. Pat. No. 5,768,535 xe2x80x9cSoftware-based encoder for a software-implemented end-to-end scalable video delivery systemxe2x80x9d. Here, the scalable property of a hierarchical image decomposition, similar to the wavelet transform, is used in conjunction with vector quantisation to produce a stream that scales in spatial and temporal resolution. At the receiving end the decoder extracts a stream with the required spatial and temporal properties. Full resolution, full frame rate images can be migrated from disk to CD-ROM to tape as they age, but can be recalled if needed.
A similar system is described in the JPEG 2000 image coding system draft specification (ISO/IEC CD15444-1: 1999). This describes a coding method for still pictures using a wavelet transform in conjunction with coefficient significance-ordering in a manner similar to the SPIHT system described above. Markers are inserted into the bitstream to allow the decoder to extract a reconstructed image of the desired quality.
Yet another approach is disclosed in U.S. Pat. No. 5,953,506 xe2x80x9cMethod and apparatus that provides a scalable media delivery systemxe2x80x9d, which describes a system for encoding multimedia data in MPEG format as a base stream and a set of additive streams that can be combined to provide various quality levels to satisfy the requirements of different clients. The invention adapts to changing network bandwidth by adding or removing streams, according to a Client-provided profile, and so increasing or reducing bit-rate. It is designed to satisfy a straightforward streaming model of media delivery, where a media steam is produced by the Server and consumed by the Decoder.
The five prior art disclosures described above are designed to present media to a client over a network in a more user-friendly manner than previously, removing, to some extent, unacceptable delay due to the properties of the network. They are not designed from the point of view of a storage system, neither do they present a view of the underlying structure of the file that would allow a storage tool to determine how to degrade quality in a controllable way.
They are also specific to particular media encoding formats, in that the tools that manipulate the media in the quality domain need to know the details of the encoding scheme in order to function. Most importantly, such tools cannot be made to be independent of encoding format, and to work correctly with any media file with any media encoding.
To do these things knowledge is required of the way that a component of the media depends on other components, in order for decoding to be possible.
New systems for media manipulation require more flexibility as regards access and retrieval of material in the storage hierarchy. Such systems must be capable of the following:
Randomly to access any component of the media, where a component can be a time-ordered sequence of media parts, a media part sampled at a particular time, a spatial area within a media part, a colour within a media part, or any other aspect which can be described.
To access the above components at a quality, spatial resolution or frequency resolution specified by the client.
To allow the results of any such access to be refined in such a way as to increase the information content and consequently improve the visual quality, amount of detail, or other aspect, of the material.
To perform the above operations using format-independent tools.
In order to satisfy the requirements listed above a system is required for structuring media files of any type for the maximum flexibility of access of their constituent components.
In accordance with a first aspect of the invention, there is provided a method of storing digital data comprising the steps of:
providing a media object at a given quality level;
manipulating the media object, using a reversible function, into a first data part, from which a version of the media object can be re-generated at a given quality, the first data part being stored on a first storage medium which is accessible on-line;
manipulating the media object, using a reversible function, into a second data part, the second data part being re-combinable with the first data part to enable a version of the media object to be regenerated which is of higher quality than the quality of the version of the media object which could be re-generated using only the first data part;
transferring the second data part to a second storage medium which offers substantially cheaper storage than the first storage medium.
Hence, this invention reconciles the competing needs for low-cost storage with immediate on-line access. Typically, an implementation of the invention provides for a complete library of all media objects to be made available using an on-line accessible version of each media object. Each on-line accessible version is stored using on-line storage media.
The quality of an on-line accessible version typically reflects the perceived usefulness or relevance of the version at a given time: rarely used versions may be at a very low quality, whilst frequently used versions may be at a very high quality (and may even be retained at source quality). A high quality version (or the data needed to re-generate a high quality version, if different) of each media object is stored on lower cost media, typically near on-line or off-line media. That high quality version (or the data needed to re-generate a high quality version, if different) is accessed only when needed.
This is clearly superior to conventional archiving systems, in which there is no facility to browse on-line the entirety of a large collection of media objects, with data for less useful or relevant objects in the collection only being partly held off-line and partly on-line.
The term xe2x80x98qualityxe2x80x99 should be expansively construed to refer not only to conventional xe2x80x98qualityxe2x80x99 attributes, such as distortion, scale and temporal characteristics, but also any other characteristics which affect the usefulness of an image. Hence, for example, in an embodiment of the present invention used in a surveillance system, a low quality image might refer to an image in which no movement has been detected, whereas high quality images are those images in which movement has been detected. In such an embodiment, it is the high quality images containing movement (or the data needed to re-generate images containing movement) which may be stored on-line, whereas images showing no movement (or the data needed to re-generate images containing no movement) may be stored entirely off-line.
Preferably, any degree of compression may be applied to a media object to obtain the first data part; compressed media objects, occupying relatively little space, can be stored economically on expensive on-line storage media, yielding many of the advantages of on-line retrieval. As noted above, the ability, conventionally provided by archival systems, of recovering the source, is provided by the second data part stored on the lower cost media.
The first data part may be subject to regular, iterative manipulations, each of which further degrades quality and reduces data size, if the first data part is accessed infrequently or not at all. In this way, an intelligent media management system can be constructed which offers users the ability to browse material on-line which would conventionally have to be relegated to archival storage, but which automatically ensures that rarely accessed material is progressively degraded to a given threshold so that it occupies the minimum of expensive on-line storage resources.
Hence, for example, an entire library of digital images may be stored using this approach. Rarely used images may be manipulated into low quality digital images, which are each maintained available for on-line retrieval. Frequently used images may be subject to no such manipulation. Higher quality images of each manipulated digital image (or the data needed to re-generate each high quality version, if different) are maintained on lower cost storage media, such as near on-line (for example, juke-box CD-ROM) or archival media such as tape storage. The lower quality images are adequate for browsing and the higher quality images (or associated data), which may be at the quality of the source, are delivered to a user only when needed.
A preferred embodiment applies the concept of indexed layers of information, which are referred to as Partitions in this specification. Partitions are particularly useful since manipulation is straightforward: it can simply comprise the process of separating or splitting layers, with layers relevant to the lower quality, on-line version being split from layers relevant to the higher quality, off-line version. The inverse of the splitting process is needed to recombine previously split layers. Using a layered bitstream also removes the need to apply a separate layering process since the data is already encoded in an embedded and hierarchical object, formed with the data partitioned into a variable and ordered set of indexed layers or partitions.
Theoretically, an infinite level of partitions could be created but the practical and commercial limitations on the implementation will constrain the number of partitions to manageable and maintainable levels. With advances in digital media storage and codec technology, the number of partitions may increase as desirable.
In a sophisticated implementation, the partitioning process can be automated using defined criteria that may be a feature of an individual or a system wide profile. There are many criteria which can be used to control the process. The criteria may be held as a profile which is used to determine, for each application of the partitioning function, exactly how the object is split.
The criteria may include:
The time elapsed since object creation.
Metadata associated with the original source material.
Usage patterns.
Availability of storage.
Flags set by users to register interest.
Data access can be automatically altered by the step of viewing a version of a media object, using a defined content access model. This may be redefined by some modifier as and when required by the model. This might be limited to methods such as once a user has viewed the media for the first time his subsequent views are reduced in quality.
The present invention may be implemented on a client server network, in which the on-line accessible data (i.e. the first data part) for each media object resides on a server which is connected to one or more clients over a network. The term network should be expansively construed to cover any kind of data connection between two or more devices.
In an S.A.N (Storage Area Network) environment, for example, the deployment of the object need not be restricted to a particular media or network component; the system could choose to distribute the object. For example, in a S.A.N. which is a server cluster, the servers do not necessarily act as a resilient or fault tolerant backup, but instead offer massive parallel storage arrays through a common interface. With the present invention, objects may be split in a manner that allows for efficient and manageable use of bandwidths and media costs, since in essence it is only data that is needed that is actually moved, rather than an entire object. Hence, with partitioned data, it is possible to reduce the I/O demand for the storage sub-systems.
In another aspect of the present invention, there is a method of recovering a media object which has been stored using the above inventive methods, comprising the step of recombining the first data part and the second data part using the reverse of the function. In a further aspect, this invention encompasses digital data stored using the storage methods described above. In another aspect, there is a computer program which, when running on a client, enables the client to receive and playback a media object previously stored using any of the above methods. In a further aspect, there is a computer program which when running on a computer enables the computer to perform any of the above methods. In a penultimate aspect, a computer programmed to perform any of the inventive methods is disclosed. In a final aspect, this specification discloses a computer network comprising several computers, at least one of which performs the data storage method claimed above and enables users to access the different versions of the media object